# 433 中等：最小基因变化
from collections import deque


def minMutation(start, end, bank):
    if start == end:
        return 0
    if bank.count(end) == 0:
        return -1

    q = deque([(start, 0)])

    while q:
        cur, step = q.popleft()
        for i, c in enumerate(cur):
            for ch in 'ACGT':
                if c != ch:
                    n = cur[:i] + ch + cur[i+1:]
                    if bank.count(n):
                        if n == end:
                            return step + 1
                        bank.remove(n)
                        q.append((n, step + 1))
    return -1


print(minMutation("AACCGGTT",  "AAACGGTA",  ["AACCGGTA","AACCGCTA","AAACGGTA"]))
